/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.fjala.softure.tree.sorted;

import java.util.Iterator;
import java.util.Stack;

/**
 * Iterator that walks all the tree in a order way.
 *
 * @author Dann Meneses
 */
public class SortedBinaryTreeIterator<T extends Comparable<T>> implements Iterator<T> {

    /**
     * Start Node
     */
    private BinaryNode<T> root;
    /**
     * Queue to walk the tree and save the remaining nodes until it's their
     * turn.
     */
    private Stack<BinaryNode<T>> visiting;
    /**
     * Current node in the walking.
     */
    private BinaryNode<T> current;

    /**
     * Constructor that receives the root node of the tree.
     *
     * @param root Root node of the tree.
     */
    public SortedBinaryTreeIterator(BinaryNode<T> root) {
        this.root = root;
        visiting = new Stack<BinaryNode<T>>();
    }

    @Override
    public boolean hasNext() {
        return (root != null);
    }

    @Override
    public T next() {
        if (!hasNext()) {
            throw new java.util.NoSuchElementException("no more elements");
        }
        if (visiting.empty()) {
            pushLeftmostNode(root);
        }
        current = visiting.pop();
        T result = current.getData();

        if (current.right != null) {
            BinaryNode<T> right = current.right;
            pushLeftmostNode(right);
        }

        if (visiting.empty()) {
            root = null;
        }

        return result;
    }

    /**
     * Stacks all the left side nodes until it finds the leftmost one.
     *
     * @param node node to start the stack task.
     */
    private void pushLeftmostNode(BinaryNode<T> node) {
        if (node != null) {
            visiting.push(node);
            pushLeftmostNode(node.left);
        }
    }

    @Override
    public void remove() {
        BinaryNode<T> parent = (BinaryNode<T>) current.getParent();
        if (!current.hasChildren()) {
            parent.removeChild(current);
        } else {
            if (current.left == null) {
                parent.replaceChild(current, current.right);
                current.right.setParent(parent);
            } else {
                if (current.right == null) {
                    parent.replaceChild(current, current.left);
                    current.left.setParent(parent);
                } else {
                    BinaryNode<T> temp = current.right;

                    while (temp.right != null) {
                        temp = temp.right;
                    }
                    BinaryNode<T> oldTempParent = (BinaryNode<T>) temp.getParent();
                    oldTempParent.replaceChild(temp, null);
                    temp.setParent(parent);
                    temp.right = current.right;
                    temp.left = current.left;

                    parent.replaceChild(current, temp);
                }
            }
        }
    }

    /**
     * Gets the current node during the walking.
     *
     * @return current node.
     */
    public BinaryNode<T> getCurrent() {
        return current;
    }
}
